<html>
    <head>
        <meta charset="utf-8">
        <title>Leetcode 算法 － 1. Two Sum</title>
        <link rel="stylesheet" href="../assets/stylesheets/global.css">
        <link rel="stylesheet" href="../assets/stylesheets/words.css">
        <link rel="stylesheet" href="../assets/stylesheets/monokai.css">
        <link rel="stylesheet" href="../assets/stylesheets/table.css">
        <link rel="shortcut icon" href="../assets/images/favicon.ico" type="image/x-icon">
        <link rel="icon" href="../assets/images/favicon.ico" type="image/x-icon">
        <script>
            // 统计代码
            (function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
                (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
                m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
                })(window,document,'script','https://www.google-analytics.com/analytics.js','ga');

            ga('create', 'UA-93231524-1', 'auto');
            ga('send', 'pageview');
        </script>
    </head>
    <body>
        <div id="header">
            <a href="../index.html"><div id="logo">JG</div></a>
        </div>
        <div id="container" class="typo">
            <div id="article">
                <h1>Leetcode 算法 － 1. Two Sum</h1>
                <h4>Posted August 16, 2016</h4>

                <blockquote class="blockquote-normal">
                <p><strong>问题链接</strong>: <a href="https://leetcode.com/problems/two-sum/">1. Two Sum</a></p><br/><p><strong>问题描述</strong>: Given an array of integers, return indices of the two numbers such that they add up to a specific target.</p><br/><p>You may assume that each input would have exactly one solution.</p></blockquote>
<p><strong>Example:</strong></p>
<div class="code-wrapper"><span class="lang-label">Python</span><div class="highlight"><pre><span></span><span class="n">Given</span> <span class="n">nums</span> <span class="o">=</span> <span class="p">[</span><span class="mi">2</span><span class="p">,</span> <span class="mi">7</span><span class="p">,</span> <span class="mi">11</span><span class="p">,</span> <span class="mi">15</span><span class="p">],</span> <span class="n">target</span> <span class="o">=</span> <span class="mi">9</span><span class="p">,</span>

<span class="n">Because</span> <span class="n">nums</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span> <span class="o">+</span> <span class="n">nums</span><span class="p">[</span><span class="mi">1</span><span class="p">]</span> <span class="o">=</span> <span class="mi">2</span> <span class="o">+</span> <span class="mi">7</span> <span class="o">=</span> <span class="mi">9</span><span class="p">,</span>
<span class="k">return</span> <span class="p">[</span><span class="mi">0</span><span class="p">,</span> <span class="mi">1</span><span class="p">]</span><span class="o">.</span>
</pre></div>
</div><blockquote class="blockquote-normal">
                <p><strong>UPDATE (2016/2/13)</strong>: The return format had been changed to zero-based indices. Please read the above updated description carefully.</p></blockquote>
<p>这是我解的第一道题， 当时就懵比了, 写了若干方法均超时了. 最后到网上搜索的答案. 需要用哈希表, python 字典其实就是哈希表的实现. <strong>感受下哈希表的使用场景， 后面更多的解题都需要哈希表来完成.</strong></p>
<div class="code-wrapper"><span class="lang-label">Python</span><div class="highlight"><pre><span></span><span class="k">class</span> <span class="nc">Solution</span><span class="p">(</span><span class="nb">object</span><span class="p">):</span>
    <span class="k">def</span> <span class="nf">twoSum</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">nums</span><span class="p">,</span> <span class="n">target</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;</span>
<span class="sd">        :type nums: List[int]</span>
<span class="sd">        :type target: int</span>
<span class="sd">        :rtype: List[int]</span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="n">d</span> <span class="o">=</span> <span class="p">{}</span>
        <span class="k">for</span> <span class="n">i</span><span class="p">,</span> <span class="n">_</span> <span class="ow">in</span> <span class="nb">enumerate</span><span class="p">(</span><span class="n">nums</span><span class="p">):</span>
            <span class="n">x</span> <span class="o">=</span> <span class="n">nums</span><span class="p">[</span><span class="n">i</span><span class="p">]</span>
            <span class="k">if</span> <span class="n">target</span> <span class="o">-</span> <span class="n">x</span> <span class="ow">in</span> <span class="n">d</span><span class="p">:</span>
                <span class="k">return</span> <span class="n">i</span><span class="p">,</span> <span class="n">d</span><span class="p">[</span><span class="n">target</span> <span class="o">-</span> <span class="n">x</span><span class="p">]</span>
            <span class="n">d</span><span class="p">[</span><span class="n">x</span><span class="p">]</span> <span class="o">=</span> <span class="n">i</span>
</pre></div>
</div>
            </div>
            <div id="footer">
                <a href="../words.html"><div id="more-words">MORE WORDS</div></a>
            </div>
        </div>
    </body>
</html>